package com.black.play.entity;

import com.black.play.util.ArrayUtil;

import java.util.Random;

/**
 * @author ylx
 */
public class SudokuCreator
{
    private static final int SIZE = 9; // 数独的大小为9x9
    private static final int SUBGRID_SIZE = 3; // 子网格的大小为3x3
    private static final Random RANDOM = new Random(); // 随机数生成器

    /**
     * 生成一个完整的数独棋盘。
     * <p>
     * 该方法首先初始化一个空的数独棋盘，然后通过特定的算法填充棋盘，以生成一个完整的、符合数独规则的棋盘。
     * <p>
     *
     * @return 返回一个完全填充的数独棋盘实例。
     */
    public static SudokuBoard generateCompleteSudoku()
    {
        int[][] board = new int[SIZE][SIZE];
        // 1-9打乱初始化第一行
        for (int i = 0; i < SIZE; i++)
        {
            board[0][i] = i + 1;
        }
        // 对第一行的数字进行随机打乱，目的是为了通过不同的起始状态增加生成不同数独解的可能性
        ArrayUtil.shuffle(board[0]);
        // 生成一个完整的数独解
        solveSudoku(board);
        // 将填充好的棋盘封装成数独棋盘对象并返回
        return new SudokuBoard(board);
    }

    /**
     * 检查给定的数是否可以在数独板的指定位置上合法地放置。
     *
     * @param board 数独板的二维数组表示。
     * @param row   指定位置的行索引。
     * @param col   指定位置的列索引。
     * @param num   要检查的数。
     * @return 如果数可以在指定位置上放置，则返回true；否则返回false。
     * 方法首先检查同一行和同一列是否已经存在相同的数，
     * 然后检查所在的3x3子网格中是否已经存在相同的数。
     * 如果在任何情况下找到了相同的数，则该数不能在指定位置上放置，
     * 方法返回false；否则，方法返回true，表示该数可以放置在指定位置上。
     */
    public static boolean isValid(int[][] board, int row, int col, int num)
    {
        // 检查同一行和同一列是否有相同的数字
        for (int i = 0; i < SIZE; i++)
        {
            if (board[row][i] == num || board[i][col] == num)
            {
                return false;
            }
        }
        // 检查所在的3x3子网格是否有相同的数字
        int startRow = row - row % SUBGRID_SIZE;
        int startCol = col - col % SUBGRID_SIZE;
        for (int i = 0; i < SUBGRID_SIZE; i++)
        {
            for (int j = 0; j < SUBGRID_SIZE; j++)
            {
                if (board[startRow + i][startCol + j] == num)
                {
                    return false;
                }
            }
        }
        // 如果通过所有检查，则数字num合法
        return true;
    }

    /**
     * 解决数独问题的核心函数。
     * 通过递归回溯算法生成完整的数独解，
     * 即通过递归尝试填充空格以解决数独谜题。
     *
     * @param board 数独棋盘，表示为一个二维整数数组。
     * @return 如果找到解决方案则返回true，否则返回false。
     */
    public static boolean solveSudoku(int[][] board)
    {
        // 遍历数独棋盘的每一行和每一列
        for (int row = 0; row < SIZE; row++)
        {
            for (int col = 0; col < SIZE; col++)
            {
                // 当前位置为0表示为空，需要填充数字
                if (board[row][col] == 0)
                {
                    // 尝试从1到9填充数字
                    for (int num = 1; num <= SIZE; num++)
                    {
                        // 检查当前数字是否合法
                        if (isValid(board, row, col, num))
                        {
                            // 填充合法数字并递归尝试解决剩余空格
                            board[row][col] = num;
                            // 递归求解剩余部分
                            if (solveSudoku(board))
                            {
                                return true;
                            }
                            // 如果不能解决，回溯
                            board[row][col] = 0;
                        }
                    }
                    // 如果所有数字都不合法，返回false表示无法解决当前空格
                    return false;
                }
            }
        }
        // 如果遍历完整个棋盘且未返回false，则表示已成功解决数独
        return true;
    }

    /**
     * 从数独棋盘中随机移除数字，以创建一个具有指定数量空位的数独谜题。
     * 移除数字的过程中确保数独谜题有且仅有一个解决方案。
     *
     * @param board    二维数组表示的数独棋盘。
     * @param numHoles 需要移除的数字数量。
     */
    public static void removeNumbersFromBoard(int[][] board, int numHoles)
    {
        // 记录已移除的数字数量
        int holesMade = 0;
        // 循环直到达到指定的移除数字数量
        while (holesMade < numHoles)
        {
            // 随机选择一个位置
            int row = RANDOM.nextInt(SIZE);
            int col = RANDOM.nextInt(SIZE);
            // 如果该位置有数字
            if (board[row][col] != 0)
            {
                // 备份当前位置的数字
                int backup = board[row][col];
                // 在选中位置挖去数字（置为0）
                board[row][col] = 0;
                // 创建数独棋盘的深拷贝，用于后续检查
                int[][] boardCopy = deepCopyBoard(board);
                // 检查移除数字后的棋盘是否有且仅有一个解决方案
                SudokuSolutions solutions = new SudokuSolutions();
                solveSudokuWithCount(boardCopy, solutions);
                if (solutions.size() != 1)
                {
                    // 如果没有唯一解，恢复挖去的数字
                    board[row][col] = backup;
                }
                else
                {
                    // 如果有唯一解，增加已挖去的数字数量
                    holesMade++;
                }
            }
        }
    }

    /**
     * 深度复制一个数独棋盘。
     * <p>
     * 该方法通过系统数组复制函数实现棋盘的深拷贝，避免了原始棋盘和拷贝棋盘之间的共享引用问题。
     * 这样做可以在进行操作时，确保不会影响原始棋盘的状态，提供了数据操作的独立性。
     *
     * @param board 原始的数独棋盘数组。
     * @return 深度复制后的数独棋盘数组。
     */
    private static int[][] deepCopyBoard(int[][] board)
    {
        // 初始化一个新的二维数组，用于存放复制后的棋盘
        int[][] copy = new int[SIZE][SIZE];
        // 遍历原始棋盘的每一行
        for (int i = 0; i < SIZE; i++)
        {
            // 使用System.arraycopy进行深拷贝，避免了引用类型数据的共享问题
            System.arraycopy(board[i], 0, copy[i], 0, SIZE); // 复制每一行
        }
        // 返回复制后的棋盘
        return copy;
    }

    /**
     * 使用计数的方式解决数独问题。
     * 通过递归尝试每个未填写的数字，检查是否符合数独规则。如果找到解决方案，增加解决方案的数量。
     * 如果存在多个解决方案，则提前结束递归以避免不必要的计算。
     *
     * @param board     数独棋盘，一个二维数组，0表示待填写的位置。
     * @param solutions 存储所有解决方案的集合。
     */
    private static void solveSudokuWithCount(int[][] board, SudokuSolutions solutions)
    {
        // 遍历数独棋盘的每一行和每一列
        for (int row = 0; row < SIZE; row++)
        {
            for (int col = 0; col < SIZE; col++)
            {
                // 当前位置为空（即值为0），需要填写数字
                if (board[row][col] == 0)
                {
                    // 尝试从1到9的每个数字
                    for (int num = 1; num <= SIZE; num++)
                    {
                        // 检查当前数字是否合法
                        if (isValid(board, row, col, num))
                        {
                            // 填写当前数字，并递归解决剩余位置
                            board[row][col] = num;
                            solveSudokuWithCount(board, solutions);
                            // 如果找到多个解决方案，提前返回 不改变solutions大小
                            if (solutions.size() > 1)
                            {
                                return;
                            }
                            // 无论是否有解 都进行回溯，撤销当前数字的填写
                            board[row][col] = 0;
                        }
                    }
                    // 无解 所有数字尝试失败 则无解
                    return;
                }
            }
        }
        // 所有位置填满，数独解决成功 将解决方案添加到集合中
        solutions.addSolution(new SudokuBoard(board));
    }
}
